#define _CRT_SECURE_NO_WARNINGS 1

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
        map<Node*, Node*> m1;
        Node* CopyHead = nullptr;
        Node* tail = nullptr;

        Node* cur = head;
        while (cur)
        {
            Node* newNode = new Node(cur->val);
            if (tail == nullptr)
            {
                CopyHead = tail = newNode;
            }
            else
            {
                tail->next = newNode;
                tail = tail->next;
            }

            m1[cur] = newNode;
            cur = cur->next;
        }

        cur = head;
        Node* tCopyHead = CopyHead;
        while (cur)
        {
            if (cur->random == nullptr)
            {
                tCopyHead->random = nullptr;
            }
            else
            {
                tCopyHead->random = m1[cur->random];
            }

            cur = cur->next;
            tCopyHead = tCopyHead->next;
        }

        return CopyHead;
    }
};